package main

import "fmt"

//DFS:0ms 100%,2.4MB 64%
func movingCount(m int, n int, k int) int {
	count := 0
	square := make([][]int, m)
	for i := 0; i < m; i++ {
		square[i] = make([]int, n)
	}
	around := [][]int{{0, 1}, {1, 0}}
	var traverse func(i, j int)
	traverse = func(i, j int) {
		if square[i][j] != 0 {
			return
		}
		s := fmt.Sprintf("%v%v", i, j)
		var sum int32 = 0
		for _, v := range s {
			sum += (v - 48)
		}
		if int(sum) > k {
			square[i][j] = -1
			return
		}
		count++
		square[i][j] = count
		for _, v := range around {
			if ii, jj := i+v[0], j+v[1]; ii >= 0 && ii < m && jj >= 0 && jj < n {
				traverse(ii, jj)
			}
		}
	}
	traverse(0, 0)
	return count
}

func main() {
	fmt.Println(movingCount(4, 5, 5))
	fmt.Println('0', '5')
}
